1. Field of the Invention
The present invention relates to a multi-plane cell switch fabric system, and relates to a switch technique for dynamically and mutually connecting plural function blocks included in the inside of an apparatus such as a router, a server or a storage apparatus, and particularly to a multi-plane cell switch fabric system which uses plural independently operating switches and rearranges, when the arrival sequence of data is changed at a destination, the data in proper sequence.
2. Background Art
In a network transfer apparatus such as a router, a server apparatus, a storage apparatus to connect plural disk arrays, or the like, a switch fabric is used for performing data exchange between function blocks of the inside of the apparatus. The exchange capacity of the switch fabric is represented by the product of the number of ports and the port capacity (line speed), and in order to realize large capacity exchange, it is necessary to increase one of or both of the number of ports and the port capacity.
The number of ports can be increased by multistage-connecting element switches and by forming an omega network, a cross network, a fat-tree network or the like. Besides, although the port capacity of the switch fabric can be increased by increasing the port capacity of a switch LSI (Large Scale Integration), since the number of pins capable of being mounted on the LSI is limited by the mounting limit of the CMOS (Complementary MOS) of the times, when the large capacity port is realized, the number of ports per switch LSI is decreased.
Although the whole exchange capacity of the switch fabric can be increased by multistage-connecting the switch LSIs having a small number of large capacity ports, the following problems arise. That is, when the total number of ports is increased, the number of connection stages is increased, and there arise a problem that the latency for passing through the switch fabric becomes large. Besides, even when the destinations are different, collision occurs in the switch fabric and there arises a problem that the throughput is reduced. As a method of realizing an objective exchange capacity by avoiding these problems, a multi-plane cell switch fabric system (parallel packet switch) is known.
In the multi-plane cell switch fabric system, M relatively low speed switch LSIs each having a port with a capacity of 1/M of required capacity are prepared, input data is divided in a distributing part as an input of the switch fabric, is distributed to respective switches and is made to pass therethrough, so that desired large capacity exchange is realized. In general, in the case of a switch used for a network apparatus, input data is a variable length packet, and the packet is divided into fixed length units called cells.
When the multi-plane cell switch fabric system is constructed most easily, plural switch LSIs used for an exchange part are completely synchronized, and a completely identical destination adjustment operation is performed. Thus, since the cells arrive at a destination (output of the switch) in proper sequence at completely predictable timing, the packets can be easily restored, and further, the packet sequence in the flow can be easily restored.
However, in recent years, the port capacity and exchange capacity required for the switch become very large, and the speed of each switch LSI itself constituting the multi-plane cell switch fabric system is increased. For example, as communication between LSIs, high speed serial transmission called SerDes (SERialization/DE-Serialization) is used, and the exchange process pitch of a cell is also shortened, and accordingly, it is actually difficult to completely synchronize the respective switch LSIs. Thus, it is necessary to provide a multi-plane cell switch fabric system in which the respective switches operate asynchronously, that is, the respective switches independently perform data exchange.
Patent document 1: US 2004/0143593 (A1)
Patent document 2: WO 02/43329 (A1)
Patent document 3: U.S. Pat. No. 6,832,261 (B1)
Patent document 4: US 2004/0141510 (A1)
In the multi-plane cell switch fabric system in which the respective exchange parts asynchronously operate, it is not ensured that the transmission sequence of cells in a distributing part as an input of the switch fabric is coincident with the arrival sequence of the cells via the respective exchange parts in an alignment part as an output of the switch fabric. For example, a subsequent packet passing through a switch in a non-congestion state can overtake a preceding packet passing through a switch in a congestion state. Thus, the sequence of cells in a packet group (flow) directed to the same destination from the same transmission source is restored (flow restoration) to the original, and further, the packet must be restored (packet restoration) to the original.
US 2004/0143593 (A1) (patent document 1) discloses a method in which a sequence number (serial number) of a packet, a source number, a routing index (a value for referring to a single destination or a combination of plural destinations) and priority are used, a sufficient amount of packets of each flow are stored at a destination, and then, a packet sequence is restored to the original. However, in the packet sequence restoring method of US 2004/0143593 (A1), with respect to the flows the number of which is expressed by the product of the source number, the routing index and the priority, it is conceivable that a sufficient amount of packet holding mechanisms are required, and there is a problem that the amount of hardware can be large.
WO 02/43329 (A1) (patent document 2) discloses a method in which the same time stamp as well as a destination number, a source number, and a cell division number is added to cells generated from the same packet, a clock common to the respective parts of a switch fabric is used, a cell having an old time stamp is selected with priority in a switch, and at the destination of the switch, the cells belonging to the same flow and the packet are sequentially restored in the order in which the time stamp was added. However, in the cell and packet sequence restoring method of WO 02/43329 (A1), with respect to the flows the number of which is expressed by the product of the source number and the routing index, it is conceivable that a sufficient amount of packet holding mechanisms are required, and there is a problem that the amount of hardware can be large. Besides, also with respect to the point that the clock common to the respective parts of the switch fabric is used and the rearrangement is performed based on the time, there is a problem that it can become difficult as the transfer speed of the packet or the cell is raised.
U.S. Pat. No. 6,832,261 (B1) (patent document 3) discloses a method in which plural devices for restoring the sequence of cells and packets are used, and the sequence of the cells and packets is restored while communication is made with each other. From an example of U.S. Pat. No. 6,832,261 (B1), with respect to flows the number of which is expressed by the product of a transmission source slot (source number), a sequence number (serial number) and a destination slot (destination number), it is conceivable that a sufficient amount of packet holding mechanisms are required, and there is a problem that the amount of hardware can become large.
Besides, US 2004/0143593 (A1) and WO 02/43329 (A1) disclose that according to the load of each switch, a distribution operation is performed while taking a load balance in a distributing part as an input of a switch fabric. However, in general, when a simple load balance operation is performed, before a cell or a packet staying at a switch in a congestion state arrives at an objective destination, that is, an alignment part as an output of the switch fabric, a subsequent cell or packet can arrive via a switch in a non-congestion state. Thus, in the alignment part, in order to restore the sequence of the cells or packets, the alignment part must hold a large amount of cells or packets, and there is a problem that the amount of hardware can become large.
As described above, in the multi-plane cell switch fabric system of the related art in which the respective exchange parts asynchronously operate, although the methods of the flow restoration in the alignment part and the packet restoration are disclosed, all the methods have the problem that the amount of hardware can become large. Since the multi-plane cell switch fabric system has the original object of improving the exchange capacity of the whole switch, in order not to reduce the exchange capacity by the distribution operation and the restoration operation, a lot of hardware can be mounted. However, in order to reduce the cost of the apparatus, the multi-plane cell switch fabric system having the alignment part which can be realized by smaller-scale hardware is desired.